The present invention relates to a transformation device that is used in a cryptographic device for concealing data in data communication or storage and, more particularly, to a data transformation device suitable for use in an encryption device of a secret-key encryption algorithm which encrypts or decrypts data blocks using a secret key, and a recording medium on which there is recorded a program for execution by the data transformation device.
With a view to constructing a fast and secure secret-key encryption algorithm, a block cipher is used according to which data for encryption is split into blocks of a suitable length and encrypted for each block. Usually, the block cipher comprises a data diffusion part which randomizes input data to be encrypted, and a key scheduling part which is supplied with a secret common key (hereinafter referred to as a master key) input to the encryption device and generates a sequence of subkeys for use by the data diffusion part. A typical secret-key encryption algorithm, which is used in the data transformation device to conceal data, is DES (Data Encryption Standard) that was FIPS-approved algorithm for encryption.
FIG. 1 illustrates the functional configuration of DES. DES uses a 64-bit secret key (8 bits being used for parity), and encrypts or decrypts data in blocks of 64 bits. In FIG. 1 the encryption process is executed in a data diffusion part 10, which begins with initial permutation of 64 bits of a plaintext M in an initial permutation part 11, followed by splitting the permuted data into two pieces of 32-bit block data L0 and R0. The block data R0 is input to a function operation part (referred to also as a round function) 12 which is a data transformation part shown as an i-th round processing part 14i (i=0, 1, . . . , 15) in FIG. 2, wherein it is transformed to f(R0, k0) using a 48-bit subkey k0. The thus transformed data f(R0, k0) and the block data L0 are exclusive ORed in an XOR circuit 13, and its output and the block data R0 are swapped to obtain the next block data L1, R1. That is,
R1=L0⊕f(R0, k0)
L1=R0
where ⊕ represents an exclusive OR. A 0-th round processing part 140 comprises the function operation part 12 and the XOR circuit 13 and swaps the two pieces of block data to provide the two pieces of output block data L1 and R1; similar round processing parts 141 to 1415 are provided in cascade. The processing by the i-th round processing part 14i will hereinafter be referred to as i-th processing, where i=0, 1, . . . , 15. That is, each round processing part 14i (where 0xe2x89xa6ixe2x89xa615) performs the following processing
Ri+1Li⊕f(Ri, ki)
Li+1=Ri
And finally concatenation two pieces of data R16 and L16 into 64-bit data, which is permuted in a final permutation part 15 to provide a 64-bit ciphertext. Incidentally, the operation of the final permutation part 15 corresponds to an inverse transform of the operation of the initial permutation part 11.
The decryption process can be executed following the same procedure as that for the encryption process except inputting subkeys k0, k1, . . . , k14, k15 to the function f (the function operation part 12) in the order k15, k14, . . . , k1, k0 which is reverse to that in the encryption process. In such an instance, the outputs L16 and R16 from the final round processing part 1415 are further swapped as depicted, and in the decryption process the ciphertext is input to the initial permutation part 11 for execution of the process of FIG. 1, by which the plaintext is provided intact at the output of the final permutation part 15. In a key scheduling part 20 an expanded key generation part 21: splits a master key of 64 bits, except 8 bits used for parity, into two pieces of 28-bit right and left key data; then performs 16-round swapping of the two pieces of 28-bit right and left key data; and performs reduced permutation of the permuted right and left data (a total of 56 bits) provided from the respective rounds to generate 16 48-bits subkeys k0, k1, . . . , k14, k15 which are provided to the corresponding round processing parts of the data diffusion part 10.
The processing in the function operation part 12 is performed as depicted in FIG. 2. To begin with, the 32-bit block data Ri is transformed to 48-bit data E(Ri) in an expanded permutation part 17. This output data and the subkey ki are exclusive ORed in an XOR circuit 18, whose output is transformed to 48-bit data E(Ri)⊕ki, which is then split to eight pieces of 6-bit sub-block data. The eight pieces of sub-block data are input to different S-boxes S0 to S7 to derive therefrom a 4-bit output, respectively. Incidentally, the S-box Sj (where j=0, 1, . . . , 7) is a nonlinear transformation table that transforms the 6-bit input data to the 4-bit output data, and is an essential part that provides security of DES. The eight pieces of output data from the S-boxes S0 to S7 are concatenated again to 32-bit data, which is applied to a permutation part 19 to provide the output f(Ri, ki) from the function operation part 12 as shown in FIG. 2. This output is exclusive ORed with Li to obtain Ri+1.
Next, a description will be given of cryptanalysis techniques. A variety of cryptanalysis techniques have been proposed for DES and other traditional secret-key encryption algorithms; extremely effective cryptanalysis techniques among them are differential cryptanalysis proposed by E. Biham and A. Shmir, (xe2x80x9cDifferential Cryptanalysis of DES-like Cryptosystems,xe2x80x9d Journal of Cryptology, Vol. 4, No. 1, pp.3-72) and linear cryptanalysis proposed by Matsui, (xe2x80x9cLinear Cryptanalysis Method for DES cipher,xe2x80x9d Advances in Cryptology-EUROCRYPT"" 93 (Lecture Notes in Computer Science 765), pp. 386-397.)
Assuming that a difference between two pieces of data X and X* is defined as
xcex94X=X⊕X*,
differential cryptanalysis aims to obtain the subkey k15 in the final round processing part 1415 by applying to the following equations two sets of plaintext-ciphertext pair that an attacker possesses. In the encryption process of FIG. 1, let (Li, Ri) and (L*i, R*i) represent input data into the round processing part 14i for first and second plaintexts respectively. With the difference defined as mentioned above, the following equations hold.
xcex94Li=Li⊕L*i
xcex94Ri=Ri⊕R*i
In FIG. 1, since L15=R14, L*15=R*14, L16=R15 and L*16=R*15, the following equations hold
R16=L15⊕f(R15, k15)
R*16=L*15⊕f(R*15, k15)
and the exclusive OR of both sides of these two equations is obtained as follows:
xcex94R16=xcex94L15⊕f(L16, k15)⊕f(L16⊕xcex94L16,k15).
The exclusive ORing of its both sides with xcex94R14=xcex94L15 gives the following equation:
xe2x80x83f(L16, k15)⊕f(L16xcex94L16, k15)=xcex94R16⊕xcex94R14.
At this time, since L16, xcex94L16 and xcex94R16 are data available from the ciphertext, they are known information. Hence, if the attacker can correctly obtain xcex94R14, then only k15 in the above equation is an unknown constant; the attacker can find a correct k15 without fail by an exhaustive search for k15 using the known sets of plaintext-ciphertext pair. Accordingly, once the subkey k15 is found out, the remaining eight (i.e., 56-48) bits can easily be obtained even by another exhaustive search.
On the other hand, generally speaking, it is difficult to obtain xcex94R14 since this value is an intermediate difference value. Then, assume that each round processing is approximated by the following equations with a probability pi in the 0-th to the last round but one (i.e.; the 14-th):
xcex94Ri+1=xcex94Li⊕xcex94{f(xcex94Ri)}
xcex94Li+1=xcex94Ri+1.
The point is that, when certain xcex94Ri is input to the i-th round processing part, xcex94{f(xcex94Ri)} can be predicted with the probability pi regardless of the value of the subkey ki. The reason why such approximations can be made is that, the S-boxes, which are nonlinear transformation tables, provide an extremely uneven distribution of output differences for same input differences. For example, in the S-box S0, an input difference xe2x80x9c110100(2)xe2x80x9d is transformed to an output difference xe2x80x9c0010(2)xe2x80x9d with a probability of 1/4. Then, the approximation for each round is obtained by assuming that the S-boxes are each capable of predicting the relationship between the input difference and the output difference with a probability Psi and by combining them. Furthermore, the concatenation of such approximations in the respective rounds makes it possible to obtain xcex94R14 from xcex94L0 and xcex94R0 (xcex94L0 and xcex94R0 are data derivable from the plaintext, and hence they are known) with a probability P=Πi=013pi. Incidentally, the higher the probability P, the easier the cryptanalysis. After the subkey k15 is thus obtained, a similar calculation is made of the subkey k14 regarding it as a 15-round DES that is one round fewer than in the above; such operations are repeated to obtain the subkeys one by one to k0.
It depends on the probability P whether this cryptanalysis succeeds; the higher the probability P, the more likely the success. Biham et al. say that DES could be broken by this cryptanalysis if 247 sets of chosen plaintext-ciphertext pair are available.
Linear cryptanalysis aims to obtain subkeys by constructing the following linear approximate equation and using the maximum likelihood method with sets of known plaintext-ciphertext pair possessed by an attacker.
(L0, R0)xcex93(L0, R0)⊕(L16, R16)xcex93(L16, R16)=(k0, k1, . . . , k15)xcex93(k0, k1, . . . , k15)
where xcex93(X) represents the vector that chooses a particular bit position of X, and it is called a mask value.
The role of the linear approximation expression is to approximately replace the cryptographic algorithm with a linear expression and separate it into a part concerning the set of plaintext-ciphertext pairs and a part concerning the subkeys. That is, in the set of plaintext-ciphertext pairs, the all exclusive Ors between the values at particular bit positions of the plaintext and those of the ciphertext take a fixed value, which indicates that it equals the exclusive OR of the values at particular positions of the subkeys. This means that the attacker gets information
(k0, k1, . . . , k15)xcex93(k0, k1, . . . , k15) (one bit)
from information
(L0, R0)xcex93(L0, R0)⊕(L16, R16)xcex93(L16, R16).
At this time, (L0, R0) and (L16, R16) are the plaintext and the ciphertext, respectively, and hence they are known. For this reason, if the attacker can correctly obtain xcex93(L0, R0), xcex93(L16, R16) and xcex93(k0, k1, . . . , k15), then he can obtain (k0, k1, . . . , k15)xcex93(k0, k1, . . . , k15) (one bit).
In DES only S-boxes perform nonlinear transformation; hence, if linear representations can be made for only the S-boxes, the linear approximation expression can easily be constructed. Then, assume that the each S-box can be linearly represented with a probability psi. The point here is that when the input mask value for the S-box is given, its output mask value can be predicted with the probability psi. The reason for this is that the S-boxes, which form a nonlinear transformation table, provide an extremely uneven distribution of output mask values according to the input mask values. For example, in the S-box S4, when the input mask value is xe2x80x9c010000(2),xe2x80x9d an output mask value xe2x80x9c1111(2)xe2x80x9d is predicted with a probability 3/16. By combining the mask values in these S-boxes, a linear representation of each round with the input and output mask values can be made with a probability pi, and by concatenating the linear representations of the respective rounds, xcex93(L0, R0), xcex93(L16, R16)and xcex93(k0, k1, . . . , k15) are obtained wit the following probability:
P=1/2+215Πi=015|pixe2x88x921/2|.
The higher the probability P, the easier the cryptanalysis.
According to Matsui, he has succeeded in the analysis of DES by this cryptanalysis using 243 sets of known plaintext-ciphertext pair.
To protect ciphers against the above cryptanalysis techniques, the probability P needs only to be reduced to be sufficiently small. A wide variety of proposals have been made to lessen the probability P, and the easiest way to provide increased security in the conventional cryptosystems is to increase the number of rounds. For example, Triple-DES with three DESs concatenated is an algorithm that essentially increases the number of rounds from 16 to 48, and it provides a far smaller probability P than does DES.
However, to increase the number of rounds with a view to avoiding the cryptanalysis techniques described above inevitably sacrifices the encryption speed. For example, if the number of rounds is tripled, the encryption speed is reduced down to ⅓. That is, since the encryption speed of the present DES is about 10 Mbps on the Pentium PC class, the encryption speed of Triple-DES goes down to around 3.5 Mbps. On the other hand, networks and computers are becoming increasingly faster year by year, and hence there is also a demand for data transformation devices that keep up with such speedups. With conventional data transformation devices, it is extremely difficult, therefore, to simultaneously meet the requirements of security and speedup.
Moreover, according to differential and linear cryptanalysis, the subkey in the final round is obtained as described above. Since DES has a defect that the main key can easily be derived from the subkey in the final round, there is proposed in U.S. Pat. No. 4,850,019: a method which provides increased security by increasing the complexity of the correspondence between the subkeys and the main key in the key scheduling part 20. Its fundamental configuration is shown in FIG. 3. In the above-mentioned U.S. patent, the subkeys are generated from the main key by data diffusion parts (fk), therefore it is expected that the main key cannot easily be derived from the subkeys.
Next, a description will be given, with reference to FIG. 3, of the general outlines of a key scheduling part 20 disclosed in the above-mentioned U.S. patent. An expanded key generation part 21 comprises N/2 (N=16, for example) rounds of key processing parts 210 to 21N/2xe2x88x921 which have key diffusion parts 220 to 22N/2xe2x88x921, respectively. The key processing parts 21j (where j=0, 1, . . . , N/2xe2x88x921) each perform diffusion processing of two pieces of 32-bit right and left key data, and interchange them to provide two pieces of right and left key data for input to the next-round key processing part 21j+1. The key processing parts 21j, except the first round, each have an exclusive OR part 23j, which calculates the exclusive OR of the left input key data to the key processing part 21jxe2x88x921 of the preceding round and the left output key data therefrom and provides the calculated data to the key diffusion part 22j. The left input key data of the key processing part 21j is diffused by the output from the exclusive OR part 23j in the key diffusion part 22j, from which the diffused data is output as right key data for input to the next round, and the right input key data of the key processing part 21j is output as left key data for input to the next round. The output from each key diffusion part 22j is bit-split into two subkeys Q2j and Q2j+1 (that is, ki and ki+1), which are provided to the corresponding (i=2j)-th round processing part and (i+1=2j+1)-th round processing part in FIG. 1.
The 64-bit main key is split into two pieces of 32-bit right and left key data, then in the first-round key processing part 210 the left key data is diffused by the right key data in the key difflusion part 220 to obtain diffused left key data, and this diffused left key data and the right key data are interchanged and provided as right and left key data next to the key processing part 211. The outputs from the key diffusion parts 220 to 22N/2xe2x88x921 of the key processing parts 210 to 21N/2xe2x88x921 are applied as subkeys k0 to kNxe2x88x921 to the corresponding round processing parts 140 to 14Nxe2x88x921 of the data diffusion part 10 depicted in FIG. 1.
In the expanded key generation part 21 of FIG. 3, however, each key diffusion part 22j is a function for generating a pair of key data (subkeys Q2j, Q2j+1) from two pieces of input data. In the case where when one of the two pieces of input data and the output data are known the other input data can be found out, if it is assumed that three pairs of subkeys (Q2jxe2x88x922 and Q2jxe2x88x921), (Q2j and Q2j+1), (Q2j+1 and Q2j+3) are known, since the output (subkeys Q2j+2 and Q2j+3) from the (j+1)-th key diffusion part 22j+1 and the one input data (subkeys Q2jxe2x88x922 and Q2jxe2x88x921) thereto are known, the other input data (i.e., the output data from the exclusive OR part 23j+1) can be obtained; and it is possible to derive, from the thus obtained data and the subkeys Q2j and Q2j+1 which constitute the one input data to the exclusive OR part 23j+1, the input data to the preceding j-th) key diffusion part 22j which constitute the other input data to the exclusive OR part 23j+1, that is, the subkeys Q2jxe2x88x924 and Q2jxe2x88x923 which constitute the output from the three-round-preceding ((jxe2x88x922)-th) key diffusion part 22jxe2x88x922. By repeating such operations in a sequential order, it is possible to determine all subkeys through data analysis only in the key scheduling part 20 without involving data analysis in the data diffusion part 10. It has been described just above that when subkeys of three consecutive rounds are known, all the subkeys concerned can be obtained, but when subkeys of two consecutive rounds, cryptanalysis will succeed even by estimating subkeys of the remaining one round by an exhaustive search.
Letting the final stage of the round processing in FIG. 1 be represented by i=N, subkeys kN and kNxe2x88x921 are easy to obtain by differential and linear cryptanalysis. By analyzing the key data in the expanded key scheduling part 21 as described above using the obtained subkeys, there is the possibility of obtaining all the subkeys concerned.
A first object of the present invention is to provide a data transformation device in which the round function f (the function operation part) is so configured as to simultaneously meet the requirements of security and speedup to thereby ensure security and permit fast encryption processing without involving a substantial increases in the number of rounds, and a recording medium having recorded thereon a program for implementing the data transformation.
A second object of the present invention is to implement a key scheduling part which does not allow ease in determining other subkeys and the master key by a mere analysis of the key scheduling part even if some of the subkeys are known.
To attain the first object of the present invention, a nonlinear function part, in particular, comprises: a first key-dependent linear transformation part which linearly transforms input data of the nonlinear function part based on first key data stored in a key storage part; a splitting part which splits the output data of the first key-dependent linear transformation part into n pieces of subdata; first nonlinear transformation parts which nonlinearly transform these pieces of subdata, respectively; a second key-dependent linear transformation part which linearly transforms respective pieces of output subdata of the first nonlinear transformation parts based on second key data; second nonlinear transformation parts which nonlinearly transform respective pieces of output subdata of the second key-dependent linear transformation part; and a combining part which combines output subblocks of the second nonlinear transformation part into output data of the nonlinear function part; and the second key-dependent linear transformation part contains a linear transformation part which performs exclusive ORing of its inputs which is defined by an nxc3x97n matrix.
According to the present invention, it is guaranteed that when the differential probability/linear probability in the first and second nonlinear transformation parts is p ( less than 1), the differential probability/linear probability of approximating each round is pixe2x89xa6p2 (when the input difference to the function f(the nonlinear function part) is not 0 in the case of differential cryptanalysis, and when the output mask value from the function is not 0 in the case of linear cryptanalysis). And when the function f is objective, if the number of rounds of the cryptographic device is set at 3r, then the probability of the cipher becomes Pxe2x89xa6pi2rxe2x89xa6p4r. Furthermore, if the second key-dependent linear transformation part in the case of n=4, in particular, has a configuration that exclusive ORs combination of three of four pieces of subdata with one of four pieces of key data, the probability of approximating each round is pixe2x89xa6p4 and the probability of the cipher is Pxe2x89xa6pi2rxe2x89xa6p8r. If the second key-dependent linear transformation part in the case of n=8 has a configuration that exclusive ORs combination of six or five of eight pieces of subdata with one of eight pieces of key data, the probability of approximating each round is pixe2x89xa6p5 and the probability of the cipher is Pxe2x89xa6pi2rxe2x89xa6p10r.
Moreover, the first and second nonlinear transformation parts are arranged so that their processing can be performed completely in parallelxe2x80x94this contributes to speedup.
It is possible, therefore, to construct a fast and source nonlinear function against differential and linear cryptanalysis, and to permit the implementation of a data transformation device which copes with both security and speedup.
To attain the second object of the present invention, the key scheduling part is provided with: a G-function parts which perform the same function as that of the key diffusion part (the function fk), L components which are output from the G-function parts being once stored in a storage part; and an H-function part which reads out a required number of L components from the storage part and generates subkeys by extracting the respective L components as uniformly as possible. Furthermore, in the H-function part partial information, which is used as subkeys, is extracted from the L components which are outputs from the G-function parts, then the extracted information is stored in a storage part, and the subkeys are generated by extracting the partial information from the required number of L components.